package com.jml.二期.树.红黑树;


import java.util.TreeMap;

/**
 * @author:jml
 * @date: 2019/11/26 9:55
 * @description：
 */
public class RedBlackTree {
	
	/**
	 * 当前的根节点
	 */
	private Node root;
	
	
	class Node{
		
		/**
		 * 节点的存的值
		 */
		private  int value;
		
		/**
		 * 左子树
		 */
		private Node left;
		
		/**
		 * 右子树
		 */
		private Node right;
		
		/**
		 * 节点颜色
		 */
		private NodeColor color;
		
		/**
		 * 记录当前节点父亲 没有父亲的情况下能够根节点
		 */
		private Node parent;
	}
	
	/**
	 * @Description:添加节点
	 * @param value
	 * @return:void
	 */
	public void insert(int value){
		//设置根节点
		if(this.root==null){
			Node newNode = new Node();
			newNode.parent = null;
			//根节点一定是黑色
			newNode.color = NodeColor.black;
			// 设置我们的根节点value值
			newNode.value = value;
			// 指定了我们的根节点
			this.root = newNode;
		}else{
			// 已经存在根节点 二叉搜索树啦~~
			//插入时候只有根节点默认是黑色的，其他的节点都默认是红色
			Node node = insertValue(value);
			// 当前节点判断成功时候 开始对我们的这个节点实现 变色或者旋转  修复
			// 红黑树修复
			repairTree(node);
			
		}
	}
	
	/**
	 * @Description:红黑树修复
	 * @param newNode  插入的节点
	 * @return:void
	 */
	private void repairTree(Node newNode) {
		//当前节点和当前节点的父节点都是红色的，此时指针处在当前节点的父节点。
		
		//如果是左旋，就以为当前节点的祖父节点为中心进行旋转
		//如果是右旋，就以当前节点的父亲节点的祖父节点进行旋转。
		if(newNode.parent.color.equals(NodeColor.red)){
			//父亲节点
			Node p = newNode.parent;
			//爷爷节点
			Node g = newNode.parent.parent;
			
			//场景一：父亲节点和当前节点都为红色的情况下， 且叔叔节点为红色的情况下，开始变颜色，
			//       把爷爷下的两个节点变为黑色,如果爷爷节点是根节点就不变色，不是根节点就改为红色
			if( (g.left!=null && NodeColor.red.equals(g.left.color)) && (g.right!=null && NodeColor.red.equals(g.left.color))){
				if(g.right!=null){
					g.right.color = NodeColor.black;
				}
				if(g.left!=null){
					g.left.color = NodeColor.black;
				}
				if(g!=root){
					g.color = NodeColor.red;
				}
				//只有旋转->变色，不可以变色->旋转
				return ;
			}
			//场景二：父亲节点和当前节点都为红色的情况下， 且叔叔节点为黑色或者为null的情况下，并且当前节点是在右子树的情况下
			if( (g.left == null || NodeColor.black.equals(g.left.color)) &&  (p.right == newNode) ){
				leftRotate(g);
				//将父节点改为黑色
				p.color = NodeColor.black;
				//将祖父节点改为红色
				g.color = NodeColor.red;
			}
		}
	}
	
	/**
	 * @Description:
	 * @param x 是旋转中心
	 * @return:void
	 */
	private void leftRotate(Node x){
		//左旋
		Node y = x.right;
		x.right = y.left;
		if(y.left!=null){
			y.left.parent = x ;
		}
		//当x是根节点的时候
		if(x.parent == null){
			this.root = y;
		}else{
			//x是左子树的时候
			if(x.parent.left==x){
				x.parent.left = y;
			}else{
				//x是右子树的时候
				x.parent.right = y;
			}
		}
		y.left = x ;
		x.parent = y;
	}
	
	/**
	 * @Description:
	 * @param value
	 * @return:com.jml.二期.树.红黑树.RedBlackTree.Node
	 */
	private Node insertValue(int value) {
		return getPosition(root, value);
	}
	
	/**
	 * @Description:
	 * @param node
	 * @param value
	 * @return:com.jml.二期.树.红黑树.RedBlackTree.Node
	 */
	private Node getPosition(Node node, int value) {
		if( value > node.value ){
			//右子树
			//右子树第一个节点
			if(node.right==null){
				Node newNode = new Node();
				newNode.parent = node;
				// 当前节点颜色默认情况下红色
				newNode.color = NodeColor.red;
				// 设置我们节点的值
				newNode.value = value;
				// 设置父亲的右边 newNode
				node.right = newNode;
				return newNode;
			}else{
				return getPosition(node.right, value);
			}
		}else{
			//左子树
			//左子树第一个节点
			if (node.left == null) {
				// 说明右边第一次赋值
				// 开始封装我们的根节点
				Node newNode = new Node();
				// 父节点为空
				newNode.parent = node;
				// 当前节点颜色默认情况下红色
				newNode.color = NodeColor.red;
				// 设置我们节点的值
				newNode.value = value;
				// 设置父亲的左边 newNode
				node.left = newNode;
				return newNode;
			} else {
				return getPosition(node.left, value);
			}
		}
	}
	
	
	
	public static void main(String[] args) {
		RedBlackTree redBlackTree = new RedBlackTree();
		redBlackTree.insert(1);
		redBlackTree.insert(2);
		redBlackTree.insert(3);
		redBlackTree.insert(0);
		redBlackTree.insert(0);
	}
}
